De club werd opgericht in 1945 en komt op dit moment uit in de Servische competitie.
Rode Ster was de belangrijkste stuwende kracht in het begin om het Landskampioenschap van Joegoslavië. Rode Ster won 15 kampioenschappen op rij tussen 1945 en 1960. In 1958 was Rode Ster het eerste team uit Joegoslavië dat in de EuroLeague Women vertegenwoordigd was. Ze haalde meteen de halve finales.
Het team was niet in staat om het nationale kampioenschap tussen 1964 en 1975 te winnen, maar bleek in de tweede helft van de jaren 1970 weer sterk genoeg om zes nationale titels op een rij te winnen. In 1979 behaalde zij haar grootste succes door het winnen van de EuroLeague Women. In de finale wonnen ze van BSE Boedapest uit Hongarije met 97 - 62.
Rode Ster bereikte opnieuw de finale om de EuroLeague Women in 1981. Dit keer verloren ze van TTT Riga uit de Sovjet-Unie met 65 - 83. De volgende jaren waren minder succesvol, en het team moest wachten tot 1990 om terug te keren naar het hoogste niveau. Ze haalde zeven keer de halve finales.
Tijdens de Oorlogen in Joegoslavië werd Rode Ster gediskwalificeerd voor de EuroLeague Women in 1993 in overeenstemming met Resolutie 757 van de VN Veiligheidsraad. Het team keerde terug naar de Europese competitie in 1996.
Belgrado
